528C - Data Center Drama - CodeForces Solution

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define rep1(i,a,b) for(register int i=a;i<b;i++)
#define rep2(i,a,b) for(register int i=a;i>=b;i--)
#define clean(x) memset(x,0,sizeof x)
#define dirty(x) memset(x,0x7f,sizeof x)
template <typename T>
inline void read(T &x){
    x=0;
    int f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    x*=f;
    return ;
}
template <typename T>
inline void write(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return ;
}
const int N=1e5+5;
int d[N],h[N],idx=1;
struct NODE{int v,nxt;}edge[N<<4];
inline void add(int u,int v){
    edge[++idx]=(NODE){v,h[u]};
    h[u]=idx;
    return ;
}
bool vis[N<<4];
int tot=0;
inline void DFS(int u){
    for(int &i=h[u];i;i=edge[i].nxt){
        int v=edge[i].v;
        if(vis[i]) continue;
        vis[i]=vis[i^1]=true;
        DFS(v);
        tot++;
        if(tot%2==1) write(u),printf(" "),write(v),puts("");
        else write(v),printf(" "),write(u),puts("");
    }
    return ;
}
int main(){
    int n,m;
    read(n),read(m);
    rep(i,1,m){
        int u,v;
        read(u),read(v);
        add(u,v),add(v,u);
        d[u]++,d[v]++;
    }
    int cnt=0;
    int lst=-1;
    rep(i,1,n)if(d[i]%2==1){
        cnt++;
        if(cnt&1) lst=i;
        else add(lst,i),add(i,lst),lst=-1,m++;
    }
    if(m%2==1) add(1,1),add(1,1),m++;
    write(m);
    puts("");
    DFS(1);
    return 0;
}